#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "unordered_map"

using namespace std;
/*HJJ QQ479287006
 *给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
//TODO 排列问题就不⽤使⽤ startIndex了
//
 

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


链接：https://leetcode.cn/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

vector<int> temp;
vector<vector<int>> ret;
vector<bool> used;

void permuteUniqueBack(vector<int> &nums, int index) {
    if (nums.size() == temp.size()) {
        ret.push_back(temp);
        return;
    }
    unordered_set<int> uset;//这里建立一个会过滤同一层 第几次进入这个函数就是第几层 这个过滤效率很低的
    for (int i = index; i < nums.size(); ++i) {
        if (used[i])
            continue;
        if (uset.find(nums[i]) != uset.end())
            continue;
        used[i] = true;
        uset.insert(nums[i]);
        temp.push_back(nums[i]);
        permuteUniqueBack(nums, index);
        temp.pop_back();
        used[i] = false;
    }

}

vector<vector<int>> permuteUnique(vector<int> &nums) {
    used.resize(nums.size() + 1, false);
    permuteUniqueBack(nums, 0);
    return ret;
}











//第二种方式 注意排序奥
//void permuteUniqueBack(vector<int>& nums,int index) {
//
//    if (nums.size()==temp.size())
//    {
//        ret.push_back(temp);
//        return ;
//    }
//

//
//    for (int i = index; i <nums.size() ; ++i) {
//
//        if (used[i])
//            continue;
//        //used[i-1]==false 注意这个是i-1 因为 i肯定是false啊
//        if(i>0&&nums[i]==nums[i-1] && used[i-1]==false) （拍玩序比较 左边和右边树枝相等 并且判断 这个树枝是不是往右边走呢 （向下走不符合））
//            continue;
//
//
//
//        used[i]=true;
//        temp.push_back(nums[i]);
//        permuteUniqueBack(nums,index);
//        temp.pop_back();
//        used[i]=false;
//    }
//
//
//}
//
//vector<vector<int>> permuteUnique(vector<int>& nums) {
//    sort(nums.begin(), nums.end()); // 排序
//
//    used.resize(nums.size(),false);
//    permuteUniqueBack(nums,0);
//
//    return ret;
//}
//if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
// continue;
//}
//如果改成 used[i - 1] == true used[i - 1] == true ， 也是正确的!，去重代码如下：
//if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
// continue;
//}
//这是为什么呢，就是上⾯我刚说的，如果要对树层中前⼀位去重，就⽤ used[i - 1] == false ，如果
// 要对树枝前⼀位去重⽤ used[i - 1] == true 。
//对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更⾼！